An essential aspect of online communication is the ability of two endpoints to establish an authenticated channel based on their respective identities. One solution to this employs public key infrastructure (PKI), wherein public keys allow end devices to be reasonably convinced that they are communicating only with each other. In this scheme, however, an endpoint and its identity are generally independent, i.e., an arbitrary identity is generated and assigned to an endpoint.
In various device authentication schemes, physical unclonable functions (PUFs) have been used such that each device has a unique identity intrinsically linked to the device. Rührmair et al. (“Modeling Attacks on Physical Unclonable Function.” Proceedings of the 17th ACM conference on Computer and communications security, CCS '10, pages 237-249, ACM. 2010) define three distinct classes of PUF devices:                A Weak PUF is typically used only to derive a secret key. The challenge space may be limited, and the response space is assumed to never be revealed. Typical constructions include the SRAM (Holcomb et al., “Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags,” In Proceedings of the Conference on RFID Security, 2007), Butterfly (Kumar et al., “Extended abstract: Butterfly PUF Protecting IP on Every FPGA,” IEEE International Workshop on Hardware-Oriented Security and Trust, pages 67-70, 2008), Arbiter (Lee et al., “A technique to build a secret key in integrated circuits for identification and authentication applications,” IEEE Symposium on VLSI Circuits: Digest of Technical Papers, pages 176-179, 2004), Ring Oscillator (Suh et al., “Physical Unclonable Functions for Device Authentication and Secret Key Generation,” Proceedings of the 44th, annual Design Automation Conference, DAC '07, pages 9-14, ACM, 2007), and Coating (Tuyls et al., “Read-Proof Hardware from Protective Coatings,” Proceedings of the 8th international conference on Cryptographic Hardware and Embedded Systems, CHES'06, pages 369-383, Springer, 2006) PUFs.        A Strong PUF is assumed to be (i) physically impossible to clone, (ii) impossible to collect a complete set of challenge response pairs in a reasonable time (typically taken to be on the order of weeks), and (iii) difficult to predict the response to a random challenge. For example, the super-high information content (SHIC) PUF described by Rührmair (“Applications of High-Capacity Crossbar Memories in Cryptography,”IEEE Trans. Nanotechnol., volume 10, no. 3:489-498, 2011) may be considered a Strong PUF.        A Controlled PUF satisfies all of the criteria for strong PUFs, and additionally implements an auxiliary control unit capable of computing more advanced functionalities to cryptographically augment protocols.        
PUF output is noisy in that it varies slightly despite evaluating the same input. This is generally addressed with fuzzy extraction, a method developed to eliminate noise in biometric measurements. (See Juels et al., “A Fuzzy Commitment Scheme,” Proceedings of the 6th ACM conference on Computer and Communications Security, CCS '99, pages 28-36, ACM, 1999). Fuzzy extraction may in part be employed within a device having a PUF such as within an auxiliary control unit, such that the output is constant for a fixed input. Fuzzy extraction (or reverse fuzzy extraction) may for example employ a “secure sketch,” as described by Juels et al. to store a sensitive value V to be reconstructed and a helper string P for recovering V. A secure sketch SS for input string O, where ECC is a binary (n, k, 2t+1) error correcting code of length n capable of correcting t errors and V←{0, 1}k is a k-bit value, may for example be defined as SS(O;V)=O⊕ECC(V). The original value V then may be reproduced given the helper string P and an input O′ within a maximum Hamming distance t of O using a decoding scheme D for the error-correcting code ECC and O′, as D(P⊕O′)=D(O⊕ECC(V)⊕O′)=V.
A physical unclonable function Pd:{0,1}κ1→{0,1}κ2 bound to a device d preferably exhibits the following properties:                1. Unclonability: Pr[dist(y,x)≤t|x←Uκ1,y←P(x), z←P′]≤ϵ1, the probability of duplicating PUF P with a clone PUF P′ such that their output distributions are t-statistically close is less than some sufficiently small ϵ1.        2. Unpredictability: It is desirable that an adversary cannot predict a device's PUF response r for a challenge c with more than negligible probability (at least without physical access to the device), and that helper data does not reveal anything to an adversary about PUF responses. Assuming that all entities are bound to probabilistic polynomial-time (PPT), i.e., can only efficiently perform computation requiring polynomially many operations with respect to a global security parameter λ (which refers to the number of bits in the relevant parameter). AdvPUF-PRED(κ2)=Pr[r=r′], denoting the probability of the adversary  guessing the correct response r of the PUF P to the challenge c, is preferably negligible in κ2. This can be assessed, for example, through a game between an adversary  and a PUF device P:{0,1}κ1{0,1}κ2 mapping input strings from the challenge space P of length κ1 to the response space P of length κ2 where λ is the security parameter for the protocol, given in unary as 1λ.        
PUF-PRED: PUF Prediction GameAdversary APUF Device P(1)ci ∈ CP ⊂ CP,→0 ≤ i ≤ poly(λ)←ri = P(ci) ∈ RP(2)RP ⊂ RP,0 ≤ i ≤ poly(λ)(3)Challenge c ∉ CP→(4)ci′ ∈ CP′ ⊂ CP,→c ∉ CP′,0 ≤ i ≤ poly(λ)←ri′= P(ci′) ∈ RP′(5)RP′ ⊂ RP,0 ≤ i ≤ poly(λ)(6)Guess r′   P(c)→
The game proceeds as follows:
1. The adversary  issues polynomially many (w.r.t. the security parameter λ) challenges ci∈P to the PUF device P, where the challenge set P is a proper subset of the entire challenge space P.                2. The PUF device P returns the responses {ri|ri←P(ci)} to .        3. The adversary  eventually outputs a challenge c that was not in the original set of challenge queries P. The adversary is not allowed to query the PUF device P on the committed challenge c.        4. The adversary  may once again issue a new set of polynomially many challenges ci′∈P′ to the PUF device P. The adversary is not allowed to query the PUF device P on the committed challenge c.        5. The PUF device P returns the responses {ri′|ri′←P(ci′)} to .        6. The adversary  eventually outputs a guess r′ for P's response to the committed challenge c.        
The adversary only wins the game when guess r′ is equal to P's actual response r←P(c) to 's committed challenge c. (As noted, the PUF's output is noisy and will vary slightly on any fixed input, so the equality is typically taken with respect to the output of a fuzzy extractor (e.g., Dodis et al., “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data,” SIAM J. Comput., volume 38, no. 1:97-139, 2008)).                3. Robustness: Pr[dist(y,z)>t|x←Uκ1,y←P(x), z←P(x)]≤ϵ2, i.e., the probability of a fixed PUF P yielding responses t-distant on the same input x is less than some sufficiently small ϵ2.        4. Indistinguishability: The output of the PUF device (typically fuzzy extractor output) preferably is computationally indistinguishable from a random string of the same length l, such that a PPT adversary 's advantage AdvPUF-IND(l) is at most negligibly more than ½. The indistinguishability of a PUF can be assessed, for example, through a game in which an adversary  is asked to differentiate between the output r of the fuzzy extractor for a PUF P and a randomly chosen string s∈{0,1}l of the same length l.        
PUF-IND: PUF Inistinguishability GameAdversary APUF Device P(1)ci ∈ CH ⊂ CP,→(Ri, Hi) ←0 ≤ i ≤ poly(λ)Gen(ri = P(c))←Hi ∈ RP ⊂ RP,(2)0 ≤ i ≤ poly(λ)(3)ci ∈ CH ⊂ CP,→0 ≤ i ≤ poly(λ)←Ri ∈ RP ⊂ RP,(4)0 ≤ i ≤ poly(λ)(5)Challenge c ∉ CH→b ∈ {0, 1}←b(s ∈ {0, 1}l)+(6)(1 − b)(Ri),Ri = Rep(P(c), Hi)(7)ci′ ∈ CH ⊂ CP,→c ≠ ci′,0 ≤ i ≤ poly(λ)←Ri′ ∈ RP ⊂ RP,(8)0 ≤ i ≤ poly(λ)(9)Guess b′   b→
This game proceeds as follows:                1. Adversary  executes the enrollment phase on any challenge ci∈P.        2. The PUF device returns the corresponding helper string Hi from the output of Gen. Denote this set of challenge-helper pairs (ci, Hi) as .        3. Adversary  now requests the PUF response ri=P(ci) for any ci∈. Denote the set of requested challenges in this step .        4. For all requests ci∈, the PUF device returns the set {ri|ri←P(ci)}.        5. Adversary  selects a challenge c∉, such that  has Hi but not Ri for c. The PUF device chooses a bit b∈{0,1} uniformly at random.        6. If b=0,  is given Ri=Rep(P(c)=ri, Hi). Otherwise, if b=1 then  is given a random string s∈{0,1}l.        7. Adversary  is allowed to query the PUF device for ci′∈ so long as no ci′=c.        8. For all requests ci′≠c, the PUF device returns the set {ri′|ri′←P(ci′)}.        9. The adversary outputs a guess bit b′, and succeeds when b′=b.Related assessments of PUFs are provided by Hori et al., “Quantitative and Statistical Performance Evaluation of Arbiter Physical Unclonable Functions on FPGAs,” 2010 International Conference on Reconfigurable Computing and FPGAS (ReConFig), pages 298-303, 2010; Maiti, A Systematic Approach to Design an Efficient Physical Unclonable Function, dissertation, Virginia Tech, 2012, and others.        
Various authentication schemes utilize zero knowledge proofs of knowledge, which is a method for proving that a given statement is true, while revealing nothing beyond this fact. The zero knowledge proof is an interaction between two parties: a prover  that wishes to establish the validity of a statement, and a verifier  that must be convinced the statement is true. The verifier should be convinced with overwhelming probability that a true statement is indeed true. With a zero knowledge proof of knowledge, the verifier could not use the messages from a previous proof to convince a new party of the statement's validity, and the messages reveal only a single bit of information: whether or not the prover  possesses the secret. There are two general classes of zero knowledge proofs: interactive zero knowledge proofs, where a series of messages are exchanged between the prover  and verifier , and non-interactive zero knowledge proofs, where the prover  conveys a single message  without interaction with , yet  is convinced that  possesses the secret. Many (interactive) zero knowledge proof systems require multiple iterations to establish the validity of a statement. That is, each interaction may succeed with some probability, even if the prover does not possess the secret (or the statement is false). Thus, if the probability of success when the statement is false is p, the protocol is run n times until 1−(p)n is sufficiently close to 1.